package binarytree

func postorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	res := []int{}

	res = append(res, postorderTraversal(root.Left)...)
	res = append(res, postorderTraversal(root.Right)...)
	res = append(res, root.Val)

	return res
}

// 迭代 用map记录
func postorderTraversal2(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	res := []int{}
	nodeMap := map[*TreeNode]struct{}{}
	stack := []*TreeNode{root}
	nodeMap[nil] = struct{}{}
	nodeMap[root] = struct{}{}

	for len(stack) != 0 {
		temp := stack[len(stack)-1]
		_, ok1 := nodeMap[temp.Left]
		_, ok2 := nodeMap[temp.Right]
		if ok1 && ok2 {
			res = append(res, temp.Val)
			stack = stack[:len(stack)-1]
		} else {
			if temp.Right != nil {
				stack = append(stack, temp.Right)
				nodeMap[temp.Right] = struct{}{}
			}
			if temp.Left != nil {
				stack = append(stack, temp.Left)
				nodeMap[temp.Left] = struct{}{}
			}
		}
	}
	return res
}

// 迭代 用nil记录
// 遇到nil，说明栈中nil左边这个节点的左右子树都遍历了
func postorderTraversal3(root *TreeNode) []int {

	res := []int{}
	if root == nil {
		return res
	}

	stack := []*TreeNode{root}

	for len(stack) != 0 {

		node := stack[len(stack)-1]

		if node != nil {
			stack = append(stack, nil)
			if node.Right != nil {
				stack = append(stack, node.Right)
			}
			if node.Left != nil {
				stack = append(stack, node.Left)
			}
		} else {
			stack = stack[:len(stack)-1]
			if len(stack) != 0 {
				res = append(res, stack[len(stack)-1].Val)
				stack = stack[:len(stack)-1]
			}
		}

	}

	return res

}
